import java.util.*;


public class Test {
    public List<String> topKFrequent(String[] words, int k) {
        //1. 放入Map
        Map<String,Integer>map=new HashMap<>();
        for (String tmp:words) {
            if(!map.containsKey(tmp)){
                map.put(tmp,1);
            }else{
                map.put(tmp,map.get(tmp)+1);
            }
        }
        //2. 建堆 根据键值对的value进行调整建堆
       PriorityQueue<Map.Entry<String, Integer>>priorityQueue=new PriorityQueue<>
               (k, new Comparator<Map.Entry<String, Integer>>() {
           @Override
           public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
               //如果value相同以key为基准建立大根堆
               if(o1.getValue().compareTo(o2.getValue())==0){
                   return o2.getKey().compareTo(o1.getKey());
               }
               //以value为基准的小跟堆
               return o1.getValue().compareTo(o2.getValue());
           }
       });


        //3.遍历键值对 Top-K问题
        for (Map.Entry<String, Integer>tmp:map.entrySet()) {
            //将前k个入队
            if(priorityQueue.size()<k){
                priorityQueue.offer(tmp);

            }else{
                //k+1个要用Top-k方式判断
                Map.Entry<String, Integer>cur=priorityQueue.peek();
                if(tmp.getValue().compareTo(cur.getValue())>0){
                    //说明堆顶要出队，并且将k+1入队
                    priorityQueue.poll();
                    priorityQueue.offer(tmp);
                }else{
                    //小于直接下一个
                    //等于需要判断key字典顺序
                    if(tmp.getValue().equals(cur.getValue())){
                        //tmp比cur字典顺序优先 cur要出队
                        if(tmp.getKey().compareTo(cur.getKey())<0){
                            priorityQueue.poll();
                            priorityQueue.offer(tmp);
                        }
                    }

                }
            }
        }

        //4. 出队
        List<String>list=new ArrayList<>();
        for (int i = 0; i <k ; i++) {
            list.add(priorityQueue.poll().getKey());
        }
        //逆序list
        Collections.reverse(list);
        return list;
    }

    public static void main(String[] args) {
        Test test=new Test();
        String[]word={"i", "love", "leetcode", "i", "love", "coding"};
        System.out.println(test.topKFrequent(word, 3));

    }

}
